/**
 * 贪心算法，遇到负数则从下一位数重新开始累加，将 sum 重置为0
 * @param {number[]} nums
 * @return {number}
 */

const maxSubArray = nums => {

  let max = -Infinity, sum = 0
  
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]
    if (sum > max) {
      max = sum
    }
    if (sum <= 0) {
      sum = 0
    }
  }
  return max
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
